package _02_第二季._01_排序;

import _02_第二季._01_排序.Sort;

public class QuickSort06<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        sort(0,array.length);
    }

    /**
     * 对 [begin,end) 范围内的元素进行快速排序
     * @param begin
     * @param end
     */
    private void sort(int begin,int end){
        if(end - begin<2) return;

        int mid = pivot(begin, end);

        sort(begin,mid);
        sort(mid+1,end);
    }

    /**
     * 构造出 [begin,end)范围内的轴点元素，并进行排序
     * @param begin
     * @param end
     * @return 最终轴点元素所在的位置
     */
    private int pivot(int begin,int end){
        swap(begin,begin+(int)(Math.random()*(end - begin)));
        E pivot = array[begin];
        end--;
        while(begin<end){
            while(begin<end){
                if(cmp(pivot,array[end])<0){
                    end--;
                }else{
                    array[begin++] = array[end];
                    break;
                }
            }

            while(begin<end){
                if(cmp(pivot,array[begin])>0){
                    begin++;
                }else{
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        array[begin] = pivot;
        return begin;
    }
}
